//
// Created by xili on 2024/8/5 21:39.
// Go big or go home.
//
#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
private:
    int father[210]; // 题目1 <= n <= 200
    int n; // 边的数量

    // 并查集初始化
    void init() {
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }

public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        init();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j]) join(i, j);
            }
        }
        // 此时已经并查集已经把边链接好了
        unordered_set<int> uset; // 容积有多少个没有链接的省份
        for (int i = 0; i < n; i++) {
            uset.insert(find(i));
        }
        return uset.size();
    }
};
